package com.fufu.algorithem.sort;

import java.util.Arrays;

/**
 * 选择排序
 * @author: BlcakTiger
 * @date: 2023/2/24 9:51
 * @contact: hsf6661@163.com
 */
public class Selection {

    public static void main(String[] args) {
//        int[] arr = {1,5,2,9,7};
//        System.out.println("交换前："+Arrays.toString(arr));
//        sort(arr);

        //初始化数组
        int[] arr = new int[80000];
        //随机赋值
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random()*1000000);
        }
        //记录执行排序前的时间
        long ori = System.currentTimeMillis();
        //排序
        sort(arr);
        //记录排序后的时间
        long cur = System.currentTimeMillis();
        //计算时间
        System.out.println((cur-ori)*1.0/1000);

    }

    public static void sort(int[] arr){
        //记录当前一轮的最大值索引
        int index ;
        //n个数只需要查询n-1次
        for (int i = 0; i < arr.length-1; i++) {
            //每次选择，index都从第一个元素开始，分别与后面每一个元素比较
            index = i;
            for (int j = i+1; j <arr.length ; j++) {
                //记录最大的元素索引
                if (arr[j]< arr[index]){
                    index = j;
                }
            }
            //优化：如果index不等于i，说明有index指向了更大的数，交换i与index元素的位置
            //     否则就不交换，无效的交换没有意义，应该避免这样的操作
            if (index!=i) {
                arr[i] = arr[i] ^ arr[index];
                arr[index] = arr[i] ^ arr[index];
                arr[i] = arr[i] ^ arr[index];
            }
//                System.out.println("第"+(i+1)+"轮交换："+Arrays.toString(arr)+"    "+arr[i]+"与"+arr[index]+"交换");
//            }else {
//                System.out.println("第"+(i+1)+"轮不需要交换");
//            }

        }
    }
}
